﻿// 0811train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <limits>

using namespace std;

/*
 某个充电站，可提供n个充电设备，每个充电设备均有对应的输出功率。
任意个充电设备组合的输出功率总和，均构成功率集合P的一个元素。
功率集合P的最优元素，表示最接近充电站最大输出功率p_max的元素。

输入描述
输入为3行：
第一行：充电设备个数n
第二行：每个充电设备的输出功率
第三行：充电站最大输出功率p_max

输出描述
功率集合P的最优元素
补充说明：
1. 充电设备个数n > 0
2. 最优元素必须小于或等于充电站最大输出功率p_max

输入
3
1 2 3
5
输出
5

 */
void solve01(vector<int>&item_vec, int target)
{
	int dp_size = item_vec.size() + 1;
	int target_size = target + 1;
	vector<int>target_vec(target_size, 0);
	vector<vector<int>>dynamic_grid(dp_size, target_vec);

	//边界情况
	//dp[i][0]=0 dp[0][w]=0

	for (int i=1; i<dp_size; i++)
	{
		for (int w=0; w<target_size; w++)
		{
			//动态转移方程
			//不取，继承i-1 取dp[i-1][w-curr_w]+curr_w
			//dp[i][w]=max(dp[i-1][w],dp[i-1][w-curr_w]+curr_w)
			int curr_w = item_vec[i - 1];
			if (w<curr_w)
			{
				dynamic_grid[i][w] = dynamic_grid[i - 1][w];
			}
			else
			{
				int max_prev = max(dynamic_grid[i - 1][w], dynamic_grid[i - 1][w - curr_w] + curr_w);
				dynamic_grid[i][w] = max_prev;
			}
		}
	}

	cout << dynamic_grid[dp_size - 1][target];


	//solve01------
}


/*
 已知该软盘容量为1474560字节。文件占用的软盘空间都是按块分配的，每个块大小为512个字节。
 一个块只能被一个文件使用。拷贝到软盘中的文件必须是完整的，且不能采取任何压缩技术。

输入描述
第1行为一个整数N，表示计算机中的文件数量。1 ≤ N ≤ 1000.
接下来的第2行到第N+1行(共N行)，每行为一个整数，表示每个文件的大小Si，单位为字节。
0 ≤ i < N,0 ≤ Si <= 1474560
输出描述
科学家最多能拷贝的文件总大小

示例1：
输入
3
737270
737272
737288
输出
1474542

 */

void solve02(vector<double>&double_vec)
{
	//1474560 512
	int target = floor(1474560 / 512); //2880
	int vec_size = double_vec.size();
	vector<int>item_vec(vec_size);

	for (int i=0; i<vec_size; i++)
	{
		item_vec[i] = ceil(double_vec[i] / 512);
		//cout << 512 * item_vec[i] << ' ';
	}

	vector<vector<int>>file_vec(vec_size,vector<int>(2));
	for (int i=0; i<vec_size; i++)
	{
		int real_num = floor(double_vec[i]);
		file_vec[i] = { item_vec[i], real_num };
	}
	int dp_size = double_vec.size() + 1;
	int count_size = target + 1;
	vector<vector<int>>count_vec(count_size, vector<int>(2, 0));
	vector<vector<vector<int>>>dynamic_grid(dp_size, count_vec);

	//边界情况
	//dp[i][0]=0 dp[0][w]=0

	//转移方程
	//dp[i][w]=max(dp[i-1][w], dp[i-1][w-curr_w]+curr_w
	//记录实际文件大小//3重数组
	for (int i=1; i<dp_size; i++)
	{
		for (int w=0; w<count_size; w++)
		{
			int curr_need_num = file_vec[i-1][0];
			int curr_real_num = file_vec[i-1][1];

			if (w<curr_need_num)
			{
				//继承i-1
				dynamic_grid[i][w][0] = dynamic_grid[i - 1][w][0];
				dynamic_grid[i][w][1] = dynamic_grid[i - 1][w][1];
				continue;
			}

			int inherit_num = dynamic_grid[i - 1][w][0];
			int contain_num = dynamic_grid[i - 1][w - curr_need_num][0] + curr_need_num;

			if (inherit_num>contain_num)
			{
				//继承i-1
				dynamic_grid[i][w][0] = dynamic_grid[i - 1][w][0];
				dynamic_grid[i][w][1] = dynamic_grid[i - 1][w][1];
				continue;
			}
			dynamic_grid[i][w][0] = dynamic_grid[i - 1][w - curr_need_num][0] + curr_need_num;
			dynamic_grid[i][w][1] = dynamic_grid[i - 1][w - curr_need_num][1] + curr_real_num;
		}
	}

	cout << dynamic_grid[dp_size - 1][target][1];
	//solve02------
}


void solve21(vector<int>& item_real_vec)
{
	int target = floor(1474560 / 512); //2880
	int vec_size = item_real_vec.size();
	vector<int>item_block_vec(vec_size);

	for (int i = 0; i < vec_size; i++)
	{
		item_block_vec[i] = ceil(static_cast<double>(item_real_vec[i]) / 512);
	}
	int dp_size = vec_size + 1;
	int target_size = target + 1;

	vector<int>target_vec(target_size, 0);
	vector<vector<int>>dynamic_grid(dp_size, target_vec);

	for (int i=1; i<dp_size; i++)
	{
		for (int w=0; w<target_size; w++)
		{
			int curr_block_w = item_block_vec[i - 1];
			int curr_real_w = item_real_vec[i - 1];

			if (w<curr_block_w)
			{
				dynamic_grid[i][w] = dynamic_grid[i - 1][w];
			}
			else
			{
				int inherit = dynamic_grid[i - 1][w];
				
				dynamic_grid[i][w] = max(inherit, dynamic_grid[i - 1][w - curr_block_w] + curr_real_w);
			}

		}

	}
	cout<< dynamic_grid[dp_size - 1][target];
	
	//solve21------
}


/*
 工作清单内包含n项工作，每项工作都有对应的耗时时长(单位h)和报酬，
 工作的总报酬为所有已完成工作的报酬之和。
 那么请你帮小明安排一下工作，保证小明在指定的工作时间内工作收入最大化。

输入描述
输入的第一行为两个正整数T，n。T代表工作时长(单位h，0 < T < 100000) , n代表工作数量(1  < n < 3000)
接下来是n行，每行包含两个整数t，w。t代表该项工作消耗的时长(单位h，t > 0) ，w代表该项工作的报酬。

输出描述
输出小明指定工作时长内工作可获得的最大报酬。

示例1
输入
40 3
20 10
20 20
20 5
输出
30

工作时长40 工作数量3
消耗时长20 报酬10
 */
void solve03(int target, vector<int>&item_vec, vector<int>&value_vec)
{
	//不超过target情况下，value最大
	//int curr_w=item_vec[i];int curr_value=value_vec[i]
	//dp[i][w] = max(dp[i-1][w], dp[i-1][w-curr_w]+curr_value)

	//边界情况
	//dp[i][0]=0 dp[0][w]=0
	int dp_size = item_vec.size() + 1;
	int target_size = target + 1;
	vector<int>target_vec(target_size, 0);
	vector<vector<int>>dynamic_grid(dp_size, target_vec);

	for (int i=1; i<dp_size; i++)
	{
		for (int w=0; w<target_size; w++)
		{
			int curr_w = item_vec[i - 1];
			int curr_value = value_vec[i - 1];
			if (w<curr_w)
			{
				//不取curr_w，继承i-1
				dynamic_grid[i][w] = dynamic_grid[i - 1][w];
			}
			else
			{
				int inherit = dynamic_grid[i - 1][w];
				dynamic_grid[i][w] = max(inherit, dynamic_grid[i - 1][w - curr_w] + curr_value);
			}
		}

	}
	cout << dynamic_grid[dp_size-1][target];
	//solve03------
}


/*
 现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。
输入描述
第一行客户预算 M，其中 0 <= M <= 1000000
第二行给出售价表，P1, P2, …, Pn, 其中 Pi 为充值 i 元获得的短信条数。 
1 <= Pi <= 1000， 1 <= n <= 100

输出描述
最多获得的短信条数

输入
6
10 20 30 40 60
输出
70
 */

void solve04(int target, vector<int>&item_vec)
{
	//curr_w = i; curr_value = item_vec[i]
	int vec_size = item_vec.size();
	int dp_size = vec_size + 1;
	int target_size = target + 1;
	//边界情况
	//dp[i][0]=0 dp[0][i]=0
	vector<int>target_vec(target_size, 0);
	vector<vector<int>>dynamic_grid(dp_size, target_vec);

	for (int i=1; i<dp_size; i++)
	{
		for (int w=0; w<target_size; w++)
		{
			int curr_w = i, curr_value = item_vec[i-1];
			if (w<curr_w)
			{
				//不取curr_w，继承i-1
				dynamic_grid[i][w] = dynamic_grid[i - 1][w];
			}
			else
			{
				int inherit = dynamic_grid[i - 1][w];
				dynamic_grid[i][w] = max(inherit, dynamic_grid[i][w - curr_w] + curr_value);
			}

		}

	}

	//for (auto&mini_vec:dynamic_grid)
	//{
	//	for (auto&num:mini_vec)
	//	{
	//		cout << num << ' ';
	//	}
	//	cout << '\n';
	//}
	


	cout << dynamic_grid[dp_size - 1][target];
	//solve04
}


int main()
{
	{
		//6
		//10 20 30 40 60
		//15
		//10 20 30 40 60 60 70 80 90 100
		int target = 15;
		vector<int>item_vec = { 10,20,30,40,60,60,70,80,90,100 };
		//int target;
		//cin >> target;
		//cin.ignore();

		//string input;
		//getline(cin, input);
		//stringstream oh_sstream(input);
		//vector<int>item_vec;
		//string token;
		//while (oh_sstream>>token)
		//{
		//	item_vec.push_back(stoi(token));
		//}

		//for (auto&num:item_vec)
		//{
		//	cout << num << ' ';
		//}


		solve04(target, item_vec);

		return 0;
	}

	{
		//40 3
		//20 10
		//20 20
		//20 5
		//int target = 40;
		//vector<int>item_vec = {20, 20, 20};
		//vector<int>value_vec = {10, 20, 5};
		int target, vec_size;
		cin >> target >> vec_size;
		vector<int>item_vec(vec_size);
		vector<int>value_vec(vec_size);

		for (int i=0; i<vec_size; i++)
		{
			cin >> item_vec[i];
			cin >> value_vec[i];
		}

		//for (auto&num: item_vec)
		//{
		//	cout << num << ' ';
		//}
		//for (auto& num : value_vec)
		//{
		//	cout << num << ' ';
		//}

		solve03(target, item_vec, value_vec);
		return 0;
	}

	{
		//vector<int>item_vec = { 737270,737272,737288 };
		int vec_size;
		cin >> vec_size;
		vector<int>item_vec(vec_size);
		for (int i = 0; i < vec_size; i++)
		{
			cin >> item_vec[i];
		}
		solve21(item_vec);
		return 0;
	}

	{
		//vector<int>&item_vec
		//737270 737272 737288
		//400000 200000 200000 200000 400000 400000 1400000
		//vector<double>item_vec = { 400000,200000,200000,200000,400000,400000 };
		int vec_size;
		cin >> vec_size;
		vector<double>item_vec(vec_size);
		for (int i=0; i<vec_size; i++)
		{
			cin >> item_vec[i];
		}

		//for (auto&num:item_vec)
		//{
		//	cout << num << ' ';
		//}

		solve02(item_vec);
		
		return 0;
	}

	//3
	//1 2 3
	//5
	//2 3 10
	//9
	//vector<int>item_vec = { 2,3,10 };
	//int target = 9;
	int vec_size, target;
	cin >> vec_size;
	vector<int>item_vec(vec_size);
	for (int i=0; i<vec_size; i++)
	{
		cin >> item_vec[i];
	}
	cin >> target;

	//for (auto&num:item_vec)
	//{
	//	cout << num << ' ';
	//}

	solve01(item_vec, target);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
